package leecode

import "container/list"

func expandBinaryTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	queue := list.New()
	queue.PushBack(root)
	for queue.Len() != 0 {
		size := queue.Len()
		for i := 0; i < size; i++ {
			node := queue.Remove(queue.Front()).(*TreeNode)
			if node.Left != nil {
				queue.PushBack(node.Left)
				temp := &TreeNode{
					Val:  -1,
					Left: node.Left,
				}
				node.Left = temp
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
				temp := &TreeNode{
					Val:   -1,
					Right: node.Right,
				}
				node.Right = temp
			}
		}
	}
	return root
}
